//
// Created by Incredible on 17/3/15.
//

#ifndef PRACTICE_INSERTSORTIONSORT_H
#define PRACTICE_INSERTSORTIONSORT_H

/**
 * 插入排序,改进版，利用一个单位空间，将一次交换替换为一次赋值.
 * 用途：排序数组部分区间
 *
 * @param arr
 * @param n
 */
template<typename T>
void insertionSortBeat(T arr[], int l, int r) {
    for (int i = l+1; i <= r; i++) {

        //寻找arr[i]的插入位置
        T nux = arr[i];
        int j;      //保存arr[i]应该的插入位置
        for (j = i; j > l && arr[j - 1] > nux; j--) {

            arr[j] = arr[j - 1];
        }
        //将nux 放入其应该存在的位置
        arr[j] = nux;
    }
}

#endif //PRACTICE_INSERTSORTIONSORT_H
